题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1711
《网络流建模汇总》的例题
牛放中间,食物放左边,饮料放右边
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 400+9; const int M = 1000000; const int INF = 1000000000; int S,T,f,d,n,head[N],nxt[M],to[M],flow[M],dis[N],cur[N]; queue<int> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Add_Edge(int u, int v, int f) { static int TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); dis[S] = 0; que.push(S); while (!que.empty()) { int w = que.front(); que.pop(); for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) dis[to[i]] = dis[w] + 1, que.push(to[i]); } return ~dis[T]; } int DFS(int w, int f) { if (w == T) return f; else { int ret = 0; for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp; if (!f) break; } return ret; } } inline int Dinic(){ int ret = 0; while (BFS()) { memcpy(cur,head,sizeof(head)); ret += DFS(S,INF); } return ret; } int main(){ n = read(); f = read(); d = read(); S = 0; T = N-1; for (int i=1;i<=f;i++) Add_Edge(S,i,1); for (int i=1;i<=d;i++) Add_Edge(i+f+n,T,1); for (int i=1;i<=n;i++) Add_Edge(f+i,f+n+d+i,1); for (int i=1,t1,t2;i<=n;i++) { t1 = read(); t2 = read(); for (int j=1;j<=t1;j++) Add_Edge(read(),i+f,1); for (int j=1;j<=t2;j++) Add_Edge(i+f+n+d,read()+f+n,1); } printf("%d\n",Dinic()); return 0; }
Hi there mates, good article and fastidious urging commented here, I am really enjoying by
these.
Wow, this article is nice, my sister is analyzing these kinds of things,
so I am going to inform her.
Hi colleagues, fastidious piece of writing and nice urging commented here, I am truly enjoying by these.
I believe this is one of the most significant information for me.
And i am glad studying your article. But should commentary on some basic issues,
The web site taste is great, the articles is in reality excellent :
D. Just right task, cheers
Thanks for sharing your info. I truly appreciate your efforts and I will be waiting for your next write ups thanks once again.
Wow! In the end I got a webpage from where
I be capable of truly obtain helpful data regarding my study and
knowledge.
If some one wishes expert view about blogging and site-building after that i propose him/her to go to see
this website, Keep up the pleasant job.
I know this if off topic but I’m looking into starting my own weblog and was curious
what all is required to get set up? I’m assuming having a blog like
yours would cost a pretty penny? I’m not very web savvy so I’m not 100% sure.
Any recommendations or advice would be greatly appreciated.
Many thanks
I was able to find good information from your blog articles.
An intriguing discussion is worth comment. I believe that you should write more
about this subject matter, it may not be a taboo matter but generally people do
not discuss these topics. To the next! Cheers!!
It is not my first time to visit this site, i am browsing this site dailly and take nice information from here daily.
Hey I know this is off topic but I was wondering if you knew of
any widgets I could add to my blog that automatically tweet my
newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have
some experience with something like this. Please let me
know if you run into anything. I truly enjoy reading your blog
and I look forward to your new updates.
I have been absent for some time, but now I remember why I used to love this website. Thanks , I¦ll try and check back more often. How frequently you update your site?
When I initially commented I clicked the “Notify me when new comments are added” checkbox and
now each time a comment is added I get three emails with the same comment.
Is there any way you can remove people from that service?
Cheers!
Thanks for finally writing about >【BZOJ 1711】[Usaco2007 Open] Dining吃饭 –
Qizy’s Database <Liked it!
I feel that is among the so much significant information for me.
And i’m happy reading your article. But should remark on some
basic things, The site taste is perfect, the
articles is really excellent : D. Excellent activity, cheers
Does your blog have a contact page? I’m having problems locating it but, I’d like to shoot you an email.
I’ve got some ideas for your blog you might be interested
in hearing. Either way, great blog and I look forward to seeing it develop over
time.
whoah this blog is excellent i really like studying your articles.
Keep up the great work! You realize, a lot of people are looking around for
this information, you could aid them greatly.
Thank you, I have recently been looking for info approximately this topic for a while and yours is the greatest I have discovered so far. But, what about the bottom line? Are you certain about the source?
Im obliged for the blog article.Really thank you! Keep writing.